package leetcode.weekly.week332;

import java.util.Arrays;

//Solution2Test
public class Solution2 {

	public long countFairPairs(int[] nums, int lower, int upper) {
		Arrays.sort(nums);
		long ans = 0;
		for (int i = 0; i < nums.length; i++) {
			int num = nums[i];
			int l = lower - num, r = upper - num;
			int L = L(nums, i + 1, l);
			int R = R(nums, i + 1, r);
			if (L != -1 && R != -1)
				ans += R - L + 1;
		}
		return ans;
	}

	private int R(int[] nums, int i, int R) {
		int l = i, r = nums.length - 1;
		int ans = -1;
		while (l <= r) {
			int m = ((r - l) >> 1) + l;
			if (nums[m] <= R) {
				ans = m;
				l = m + 1;
			} else {
				r = m - 1;
			}
		}
		return ans;
	}

	private int L(int[] nums, int i, int L) {
		int l = i, r = nums.length - 1;
		int ans = -1;
		while (l <= r) {
			int m = ((r - l) >> 1) + l;
			if (nums[m] >= L) {
				ans = m;
				r = m - 1;
			} else {
				l = m + 1;
			}
		}
		return ans;
	}

}
